package com.kehao.leetcode.jzoffer;

import org.junit.Test;

import java.util.Arrays;
import java.util.zip.CheckedOutputStream;

/**
 * @author Kehao.Chen
 * @version 1.0
 * @date 2022/6/22 17:43
 */
public class JZSolution020 {
    public int countSubstrings(String s) {
        int count = 0;
        boolean[][] dp = new boolean[s.length()][s.length()];
        for (int i = 0; i < s.length(); i++) {
            dp[i][i] = true;
            count ++;
        }
        for (int i = 0; i < s.length() - 1; i++) {
            dp[i][i+1] = s.charAt(i)==s.charAt(i+1);
            count += dp[i][i+1]?1:0;
        }

        for (int i = 2; i < s.length(); i++) {
            for (int j = 0; j < s.length()-i; j++) {
                dp[j][j+i] = dp[j+1][j+i-1] && s.charAt(j)==s.charAt(j+i);
                count += dp[j][j+i]?1:0;
            }
        }
        return count;
    }

    @Test
    public void test01(){
        String s = "aaa";
        System.out.println(countSubstrings(s));
    }



}
